In graph theory, the planarity testing problem asks whether, given a graph, that graph is a planar graph (can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal.
Contents |
By Fáry's theorem we can assume the edges in the graph drawing, if any, are straight line segments. Given such a drawing for the graph, we can verify that there are no crossings using well-known line segment intersection algorithms that operate in O(n log n) time. However, this is not a particularly good solution, for several reasons:
For these reasons, planarity testing algorithms take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. One of these is Kuratowski's theorem, which states that:
A graph can be demonstrated to be nonplanar by exhibiting a subgraph matching the above description, and this can be easily verified, which places the problem in co-NP. However, this also doesn't by itself produce a good algorithm, since there are a large number of subgraphs to consider (K5 and K3,3 are fixed in size, but a graph can contain 2Ω(m) subdivisions of them).
A simple theorem allows graphs with too many edges to be quickly determined to be nonplanar, but cannot be used to establish planarity. If v is the number of vertices (at least 3) and e is the number of edges, then the following imply nonplanarity:
For this reason n can be taken to be either the number of vertices or edges when using big O notation with planar graphs, since they differ by at most a constant multiple.
The classic path addition method of Hopcroft and Tarjan[1] was the first published linear-time planarity testing algorithm in 1974.
The vertex addition method began with an inefficient O(n2) method conceived by Lempel, Even and Cederbaum in 1967.[2] It was improved by Even and Tarjan, who found a linear-time solution for the s,t-numbering step,[3] and by Booth and Lueker, who developed the PQ tree data structure. With these improvements it is linear-time and outperforms the path addition method in practice.[4] This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph.[5]
In 1999, Shih and Hsu developed a planarity testing algorithm that was significantly simpler than classical methods based on a new type of data structure called the PC tree and a postorder traversal of the depth-first search tree of the vertices.[6]
In 2004, Boyer and Myrvold [7] developed a simplified O(n) algorithm, originally inspired by the PQ tree method, which gets rid of the PQ tree and uses edge additions to compute a planar embedding, if possible. Otherwise, a Kuratowski subdivision (of either K5 or K3,3) is computed. This is one of the two current state-of-the-art algorithms today (the other one is the planarity testing algorithm of de Fraysseix, de Mendez and Rosenstiehl[8][9]). See [10] for an experimental comparison with a preliminary version of the Boyer and Myrvold planarity test. Furthermore, the Boyer–Myrvold test was extended to extract multiple Kuratowski subdivisions of a non-planar input graph in a running time linearly dependent on the output size.[11] The source code for the planarity test[12][13] and the extraction of multiple Kuratowski subdivisions[12] is publicly available. Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s.[14]